The throughput of the forward channel (or downlink) of a wireless network is significantly affected by the scheduling algorithm employed by the base stations of the wireless network. A large number of algorithms have been developed for scheduling the transmissions of voice and data traffic from the base stations to the mobile stations (e.g., cell phones, wireless PCs, etc.). These scheduling algorithms generally allocate to each mobile station a time slot, a frequency assignment, or a code (e.g., Walsh code), or a combination of these elements, for receiving traffic in the forward channel.
For example, a conventional orthogonal frequency division multiple access (OFDMA) network uses a scheduling algorithm that assigns each mobile station to receive forward channel (downlink) traffic in a particular timeslot and using a particular frequency assignment. This scheduling algorithm may be represented by a two-dimensional array that has timeslots on one axis (e.g., x-axis) and frequency assignments on a second axis (e.g., y-axis). Most conventional wireless networks, including conventional OFDMA networks, use a single antenna that transmits all data in a 360 degree sweep around the base station or use a sector antenna that transmits all data in, for example, a 90 degree sector or a 120 degree sector of a base station. For these types of antennas, conventional scheduling algorithms that may be represented by the two-dimensional array describe above are sufficient.
However, the new generation of wireless networks implement multiple antennas (i.e., antenna arrays) that are capable of using beamforming to transmit to mobile stations in the forward channel. Thus, even within the same antenna sector, it is possible to transmit to two separate mobile stations using the same frequency assignment and time slot, provided the two mobile stations have a sufficient spatial separation such that different transmit beams may be used. Thus, the scheduling algorithm goes from being a two-dimensional array to being a three dimensional array in which timeslots are on one axis (e.g., x-axis), frequency assignments are on a second axis (e.g., y-axis), and space (or transmit beam) is on a third axis (e.g., z-axis).
Some of the existing literature on scheduling for wireless communication and cross-layer optimizations are summarized in review papers such as “Dynamic Slot Allocation (DSA) In Indoor SDMA/TDMA Using A Smart Antenna Base Station,” F. Shad et al., IEEE/ACM Transactions on Networking, Volume 9, Issue 1, February 2001, and “Performance Of Space-Division Multiple-Access (SDMA) With Scheduling,” H. Yin et al., IEEE Transactions on Wireless Communications, Volume 1, Issue 4, October 2002. Recently, some interesting work has appeared on the cross-layer scheduling problem specifically for SDMA applications. Some of the research addressed the downlink in OFDM/A systems, such as “System Level Performance Evaluation Of OFDMA Forward Link With Proportional Fair Scheduling,” S. Yoon et al., Wireless World Research Forum, China, February 2004. Other research addressed the downlink, such as “Data Throughput Of CDMA-HDR—A High Efficiency Data Rate Personal Communication Wireless System,” R. P. Jalali et al., IEEE Vehicular Technology Conference VTC2000—Fall 2000 and “Element of Information Theory,” T. M. Cover et al., Wiley, 1991. The Yoon and Jalali references cited above describe single antenna proportional fair schedulers.
Also, some SDMA papers for CDMA wireless networks have been presented. These papers include: 1) “An Overview Of Scheduling Algorithms In Wireless Multimedia Networks,” H. Fattah et al., Wireless Communications, IEEE [see also IEEE Personal Communications], Volume 9, Issue 5, October 2002; 2) “Scheduling Algorithms In Broadband Wireless Networks,” Y. Cao et al., Proceedings of the IEEE, Volume 89, Issue 1, January 2001; and 3) “A Combined OFDM/SDMA Approach,” P. Vandenameele et al., IEEE Journal on Selected Areas in Communications, Volume 18, Issue 11, November 2000.
In “A Simplified Opportunistic Feedback And Scheduling Scheme For OFDM,” P. Svedman, IEEE Vehicular Technology Conference VTC2004—Spring 2004, it is demonstrated that optimal slot allocation in a downlink TDMA/SDMA system based on SINR feedback from the mobile station (MS) is an NP-complete problem. This is because the spatial signatures of the different mobile stations are rarely orthogonal. This paper also showed that it is possible to achieve up to two times capacity improvement compared to random slot allocation methods.
Similarly, the paper “Attaining Both Coverage And High Spectral Efficiency With Adaptive OFDM Downlinks,” A. M. Sternad et al., IEEE Vehicular Technology Conference VTC2003—Fall, Orlando, Fla., October 2003 addresses the problem of cross-layer optimization, where physical layer spatial channel information is used to do SDMA MAC layer scheduling. The solution presented is somewhat simplified, since it assumes a fixed data rate per mobile station. Therefore, the discussion does not need to consider adaptive modulation. This means that there exists an optimum SINR per mobile station. This paper does a best-fit search to allocate SDMA users so that each user achieves an optimum SINR.
The Fatah reference cited above (i.e., “An Overview Of Scheduling Algorithms In Wireless Multimedia Networks”) discusses an HSDPA application with beamforming. The Fatah references shows that the maximum SIR method with beamforming (also known as the maximum throughput method, which exclusively serves the user with the best channel conditions and thereby starves the weaker users) does not improve the throughput significantly since self-interference is dominant. It also creates widely fluctuating inter-cell interference. The Fatah reference demonstrates that an SDMA method has double the throughput compared to the maximum SIR method with beamforming.
The Cao reference cited above (i.e., “Scheduling Algorithms In Broadband Wireless Networks”) considered the downlink CDMA2000 packet data channel (PDCH) scheduling problem using multi beam-phase sweep transmit diversity (PSTD). The Cao reference compared the optimal scheduling algorithm with a simplified greedy algorithm and also the more novel genetic algorithm. The Cao reference discloses that the so-called “greedy” algorithm is optimal for one antenna, but is sub-optimal for multiple antennas. The genetic algorithm is attractive because it offers close to optimal performance at a computational complexity saving of 1000 times relative to the optimal algorithm.
In “Directed Maximum Ratio Combining And Scheduling Of High-Rate Transmission For Data Networks”, J. Wu et al., U.S. Patent Pub. No. 2003/0016731 A1, Metawave, Jan. 23, 2003, a downlink scheduler is proposed for a CDMA2000 system. The idea is to use the correlation of spatial signatures of different mobiles as a measure to cluster mobiles. The different orthogonal clusters can then all use the same Walsh codes.
In the Sternad reference cite above (i.e., “Attaining Both Coverage and High Spectral Efficiency with Adaptive OFDM Downlinks”), the authors introduced “coordinated scheduling” between sectors of the same OFDMA cell in order to achieve an efficiency of 2.1 bps/Hz/sector for thirty (30) mobile stations. The authors proposed to increase the frequency utilization by dividing the frequency spectrum in two, reserving one group of sub-carriers to the inner cell (close to base station) and the rest to the sector edge. The inner frequency channels (sub-channels) are reused in all sectors, while the outer frequency sub-channels are allocated to every 3rd sector.
Additional references discussing schedulers include: 1) “Combined Beamforming And Scheduling For High Speed Downlink Packet Access,” A. Seeger, Proceedings of Globecom, 2003; 2) “On Generalized Optimal Scheduling Of High Data-Rate Bursts In CDMA Systems,” V. Lau et al., IEEE Transactions on Communications, Volume 51, Issue 2, February 2003; and 3) “Directed Maximum Ratio Combining And Scheduling Of High Rate Transmission For Data Networks,” J. Wu et al., U.S. Patent Pub. No. US 2003/0016731 A1, Metawave, Jan. 23, 2003.
The prior art scheduling algorithms discussed above consist of schedulers for several variations of spatial division multiple access (SDMA), time division multiple access (TDMA), orthogonal frequency division multiplexing (OFDM), and code division multiple access (CDMA). However, none of the conventional algorithms is suitable for an OFDMA wireless network that uses beamforming in the forward channel (downlink) to perform SDMA transmission. Therefore, there is a need in the art for an improved scheduler for use in OFDMA-SDMA wireless network.